package leetcode.day;

// 5194. 得到目标值的最少行动次数

/**
 * 你正在玩一个整数游戏。从整数 1 开始，期望得到整数 target 。
 * <p>
 * 在一次行动中，你可以做下述两种操作之一：
 * <p>
 * 递增，将当前整数的值加 1（即， x = x + 1）。
 * 加倍，使当前整数的值翻倍（即，x = 2 * x）。
 * 在整个游戏过程中，你可以使用 递增 操作 任意 次数。
 * 但是只能使用 加倍 操作 至多 maxDoubles 次。
 * <p>
 * 给你两个整数 target 和 maxDoubles ，返回从 1 开始得到 target 需要的最少行动次数。
 * <p>
 * <p>
 * <p>
 * 输入：target = 19, maxDoubles = 2
 * 输出：7
 * 解释：最初，x = 1 。
 * 递增 3 次，x = 4 。
 * 加倍 1 次，x = 8 。
 * 递增 1 次，x = 9 。
 * 加倍 1 次，x = 18 。
 * 递增 1 次，x = 19 。
 */
public class MinMoves {
    public static void main(String[] args) {
        System.out.println(minMoves(19, 2));
    }


    // 自顶向上贪心，因为加倍大数得到的结果快
    // 逆向思维，从目标值往下做减法，当遇到偶数的时候如果加倍次数不为0，则被除以
    public static int minMoves(int target, int maxDoubles) {
        int count = 0;
        while (target > 1) {
            if (maxDoubles == 0) {
                count += target - 1;
                break;
            }
            count++;
            // 如果是偶数
            if (target % 2 == 0) {
                maxDoubles--;
                target /= 2;
            } else {
                target--;
            }
        }
        return count;
    }
}
